#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

typedef struct StringNode
{
    char ch;                 // 存储字符
    struct StringNode *next; // 指向下一个结点
} StringNode, *LinkString;

// 1. 销毁串
void DestroyString(LinkString &S)
{
    LinkString p = S;
    while (p != NULL)
    {
        LinkString temp = p;
        p = p->next;
        free(temp);
    }
    S = NULL;
}

// 2. 初始串
bool StrAssign(LinkString &T, const char *chars)
{
    DestroyString(T);
    if (chars == NULL || *chars == '\0')
    {
        T = NULL;
        return true;
    }

    LinkString tail = NULL; // 只需tail指针
    const char *pc = chars;

    while (*pc != '\0')
    {
        LinkString newNode = (LinkString)malloc(sizeof(StringNode));
        if (newNode == NULL)
        {
            DestroyString(T);
            return false;
        }
        newNode->ch = *pc;
        newNode->next = NULL;

        if (tail == NULL)
        {                // 第一个结点
            T = newNode; // 设置头指针
            tail = newNode;
        }
        else
        {
            tail->next = newNode; // 链接到尾部
            tail = newNode;
        }
        pc++;
    }
    return true;
}

// 3. 复制串
bool StrCopy(LinkString &T, LinkString S)
{
    DestroyString(T);
    if (S == NULL)
    {
        return true;
    }

    LinkString pS = S;
    LinkString tail = NULL;  // 只需tail指针

    while (pS != NULL)
    {
        LinkString newNode = (LinkString)malloc(sizeof(StringNode));
        if (newNode == NULL)
        {
            DestroyString(T);
            return false;
        }
        newNode->ch = pS->ch;
        newNode->next = NULL;

        if (tail == NULL)  // 修复：使用tail判断首结点
        { 
            T = newNode;    // 设置头指针
            tail = newNode;  // 更新尾指针
        }
        else
        {
            tail->next = newNode;  // 链接到链表尾部
            tail = newNode;        // 更新尾指针
        }
        pS = pS->next;
    }
    return true;
}

// 4. 拼接串
bool Concat(LinkString &T, LinkString S1, LinkString S2)
{
    DestroyString(T);
    if (S1 == NULL && S2 == NULL)
    {
        return true;
    }

    LinkString tail = NULL; // 只需tail指针

    // 复制S1
    LinkString p1 = S1;
    while (p1 != NULL)
    {
        LinkString newNode = (LinkString)malloc(sizeof(StringNode));
        if (newNode == NULL)
        {
            DestroyString(T);
            return false;
        }
        newNode->ch = p1->ch;
        newNode->next = NULL;

        if (T == NULL) // 直接使用T判断
        {
            T = newNode;
            tail = newNode;
        }
        else
        {
            tail->next = newNode;
            tail = newNode;
        }
        p1 = p1->next;
    }

    // 复制S2
    LinkString p2 = S2;
    while (p2 != NULL)
    {
        LinkString newNode = (LinkString)malloc(sizeof(StringNode));
        if (newNode == NULL)
        {
            DestroyString(T);
            return false;
        }
        newNode->ch = p2->ch;
        newNode->next = NULL;

        if (T == NULL) // 直接使用T判断
        {
            T = newNode;
            tail = newNode;
        }
        else
        {
            tail->next = newNode;
            tail = newNode;
        }
        p2 = p2->next;
    }
    return true;
}

// 5. 求子串
bool SubString(LinkString &Sub, LinkString S, int pos, int len)
{
    DestroyString(Sub);
    if (S == NULL || pos < 1 || len < 0)
    {
        return false;
    }

    // 移动到pos位置
    LinkString p = S;
    int i = 1;
    while (p != NULL && i < pos)
    {
        p = p->next;
        i++;
    }

    if (p == NULL)
    { // pos超过串长
        return false;
    }

    // 开始提取子串
    LinkString tail = NULL;  // 只需tail指针
    int j = 0;
    while (p != NULL && j < len)
    {
        LinkString newNode = (LinkString)malloc(sizeof(StringNode));
        if (newNode == NULL)
        {
            DestroyString(Sub);
            return false;
        }
        newNode->ch = p->ch;
        newNode->next = NULL;

        if (tail == NULL)  // 修复：使用tail判断首结点
        {
            Sub = newNode;    // 设置头指针
            tail = newNode;   // 更新尾指针
        }
        else
        {
            tail->next = newNode;  // 链接到链表尾部
            tail = newNode;        // 更新尾指针
        }

        p = p->next;
        j++;
    }
    return true;
}

// 6. 朴素模式匹配
int Index(LinkString S, LinkString T)
{
    if (T == NULL)
    {
        return 0; // 空串是任何串的子串
    }
    if (S == NULL)
    {
        return -1; // 主串为空
    }

    LinkString pS = S;
    int pos = 1; // 记录当前匹配的主串位置

    while (pS != NULL)
    {
        LinkString pT = T;
        LinkString curr = pS;
        bool match = true;

        while (pT != NULL && curr != NULL)
        {
            if (curr->ch != pT->ch)
            {
                match = false;
                break;
            }
            pT = pT->next;
            curr = curr->next;
        }

        if (pT == NULL)
        { // T完全匹配
            return pos;
        }
        if (!match)
        {
            pS = pS->next;
            pos++;
        }
    }
    return -1; // 未找到
}

// 7. 比较串
int StrCompare(LinkString S, LinkString T)
{
    LinkString pS = S, pT = T;

    while (pS != NULL && pT != NULL)
    {
        if (pS->ch != pT->ch)
        {
            return pS->ch - pT->ch;
        }
        pS = pS->next;
        pT = pT->next;
    }

    if (pS == NULL && pT == NULL)
    {
        return 0;
    }
    else if (pS == NULL)
    {
        return -1;
    }
    else
    {
        return 1;
    }
}

// 8. 判空
bool StrEmpty(LinkString S)
{
    return (S == NULL);
}

// 9. 求串长
int StrLength(LinkString S)
{
    int len = 0;
    LinkString p = S;
    while (p != NULL)
    {
        len++;
        p = p->next;
    }
    return len;
}

// 打印串
void PrintString(LinkString S)
{
    if (S == NULL)
    {
        printf("String is empty\n");
        return;
    }

    printf("String: ");
    LinkString p = S;
    while (p != NULL)
    {
        printf("%c", p->ch);
        p = p->next;
    }
    printf("\n");
}

int main()
{
    LinkString S = NULL, T = NULL, U = NULL, Sub = NULL;

    // 初始串
    StrAssign(S, "Hello");
    StrAssign(T, "World");
    PrintString(S); // String: Hello

    // 复制串
    StrCopy(U, S);
    PrintString(U); // String: Hello

    // 拼接串
    Concat(U, S, T);
    PrintString(U); // String: HelloWorld

    // 求子串
    SubString(Sub, U, 3, 5);
    PrintString(Sub); // String: lloWo

    // 模式匹配
    int pos = Index(U, T);
    printf("'World' position: %d\n", pos); // 'World' position: 6

    // 比较串
    LinkString A = NULL, B = NULL;
    StrAssign(A, "apple");
    StrAssign(B, "banana");
    printf("Compare: %d\n", StrCompare(A, B)); // 负数（a<b）

    // 判空
    printf("S empty? %s\n", StrEmpty(S) ? "true" : "false");

    // 求长度
    printf("Length of U: %d\n", StrLength(U)); // 10

    DestroyString(S);
    DestroyString(T);
    DestroyString(U);
    DestroyString(Sub);
    DestroyString(A);
    DestroyString(B);

    return 0;
}